// Package day_14_two_point 4-func minWindow(s string, t string) string {  }
// @Title day_14_two_point
// @Description
// @Author  == 琳琳也叫王木木 ==  2021/9/7 18:35
// @Create  2021/9/7 18:35
package day_14_two_point

import "math"

//输入：s = "ADOBECODEBANC", t = "ABC"
//输出："BANC"
// 判断一个字符串是否包含另外一个字符串的所有字符
func containsString(s, t string) bool {
	// 这个map记录子串中每个字符出现的次数
	sonStrMap := make(map[byte]int, 0)
	// 这个map记录窗口中每个字符出现的次数
	mainStrMap := make(map[byte]int, 0)
	for _, j := range t {
		sonStrMap[byte(j)] += 1
	}
	for _, j := range s {
		mainStrMap[byte(j)] += 1
	}
	for k, v := range sonStrMap {
		if mainStrMap[k] < v {
			return false
		}
	}
	return true
}

// 时间不通过的AC
func MinWindow(s string, t string) string {
	if t == "" || len(t) < 1 || len(s) < len(t) {
		return ""
	}
	var ans string = "" // 最终要返回的结果字符串
	slow, fast := 0, 0
	for fast <= len(s) {
		if !containsString(s[slow:fast], t) {
			fast++
		} else {
			for containsString(s[slow:fast], t) {
				if len(ans) >= fast-slow || ans == "" {
					ans = s[slow:fast]
				}
				slow++
			}
		}
	}
	return ans
}

// 20%的AC
func MinWindow2(s, t string) string {
	ori, cnt := map[byte]int{}, map[byte]int{}
	for i := 0; i < len(t); i++ {
		ori[t[i]]++
	}

	sLen := len(s)
	len := math.MaxInt32
	ansL, ansR := -1, -1

	check := func() bool {
		for k, v := range ori {
			if cnt[k] < v {
				return false
			}
		}
		return true
	}
	for l, r := 0, 0; r < sLen; r++ {
		if r < sLen && ori[s[r]] > 0 {
			cnt[s[r]]++
		}
		for check() && l <= r {
			if r-l+1 < len {
				len = r - l + 1
				ansL, ansR = l, l+len
			}
			if _, ok := ori[s[l]]; ok {
				cnt[s[l]] -= 1
			}
			l++
		}
	}
	if ansL == -1 {
		return ""
	}
	return s[ansL:ansR]
}

// 最小覆盖子串 100%的AC
func minWindow100(s string, t string) string {
	//初步判断
	if len(s) < len(t) {
		return ""
	}

	var freq [58]int
	var need [58]int
	valid := 0 //记录t字符串不同字符的个数
	//注：记录不同字符的目的是为了可以将多个字符当成一个字符看，
	//但这一个字符也有一个值就对于need某个字符的值，那是可以把多个字符看成一个字符
	//的最小值，当freq大于need对于的字符哈希值时，也同样可以看作一个字符
	//在缩小窗口分支中的 if freq[s[l]-'A'] < need[s[l]-'A']便有所体现
	res := "" //返回结果

	for i := 0; i < len(t); i++ {
		if need[t[i]-'A'] == 0 {
			valid++ //不同字符数量增加
		}
		need[t[i]-'A']++
	}

	curr := 0     //记录当前窗口里面包含t中不同字符的个数
	l, r := 0, -1 //窗口大小[l...r]

	for l < len(s) {
		if (r+1) < len(s) && valid != curr { //保证r在扩大窗口之后不会越界
			r++              //扩大窗口
			freq[s[r]-'A']++ //增大频率
			if freq[s[r]-'A'] == need[s[r]-'A'] {
				curr++ //若两个表的值想等，则curr加一
			}
		} else {
			freq[s[l]-'A']--                     //减少频率
			if freq[s[l]-'A'] < need[s[l]-'A'] { //更新匹配条件curr
				curr--
			}
			l++ //缩小窗口
		}

		if curr == valid {
			//更新结果的两种情况：
			//1.结果仍然为空字符串
			//2.结果比当前成功匹配的窗口大小要大
			if res == "" || len(res) > (r-l+1) {
				res = s[l : r+1] //切片切取的方式来更新
			}
		}
	}

	return res
}
